package com.cn.algorithm02.class07;

import java.util.*;

/***
 * @author: hels
 * @description:
 * 做一个加强堆的题目，给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op
 * 两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
 * arr= [3,3,1,2,1,2,5…
 * op = [T,T,T,T,F,T,F…
 * 依次表示：
 * 3用户购买了一件商品
 * 3用户购买了一件商品
 * 1用户购买了一件商品
 * 2用户购买了一件商品
 * 1用户退货了一件商品
 * 2用户购买了一件商品
 * 5用户退货了一件商品…
 * 一对arr[i]和op[i]就代表一个事件：
 * 用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品
 * op[i] == F就代表这个用户退货了一件商品
 * 现在你作为电商平台负责人，你想在每一个事件到来的时候，
 * 都给购买次数最多的前K名用户颁奖。
 * 所以每个事件发生后，你都需要一个得奖名单（得奖区）。
 * 得奖系统的规则：
 * 1，如果某个用户购买商品数为0，但是又发生了退货事件，
 *      则认为该事件无效，得奖名单和上一个事件发生后一致，例子中的5用户
 * 2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
 * 3，每次都是最多K个用户得奖，K也为传入的参数
 *       如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果
 * 4，得奖系统分为得奖区和候选区，任何用户只要购买数>0，
 *       一定在这两个区域中的一个
 * 5，购买数最大的前K名用户进入得奖区，
 *       在最初时如果得奖区没有到达K个用户，那么新来的用户直接进入得奖区
 * 6，如果购买数不足以进入得奖区的用户，进入候选区
 * 7，如果候选区购买数最多的用户，已经足以进入得奖区，
 *      该用户就会替换得奖区中购买数最少的用户（大于才能替换），
 *      如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户
 *      如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户
 * 8，候选区和得奖区是两套时间，
 *      因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有
 *      从得奖区出来进入候选区的用户，得奖区时间删除，
 *      进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
 *      从候选区出来进入得奖区的用户，候选区时间删除，
 *      进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
 * 9，如果某用户购买数==0，不管在哪个区域都离开，区域时间删除，
 *      离开是指彻底离开，哪个区域也不会找到该用户
 *      如果下次该用户又发生购买行为，产生>0的购买数，
 *      会再次根据之前规则回到某个区域中，进入区域的时间重记
 * 请遍历arr数组和op数组，遍历每一步输出一个得奖名单
 **/
public class C13_BuyOrRefund {
    public static class Customer {
        public int id;
        public int buy;
        public int enterTime;

        public Customer(int id, int buy, int enterTime) {
            this.id = id;
            this.buy = buy;
            this.enterTime = enterTime;
        }
    }

    public static class CandidateComparator implements Comparator<Customer> { // 购买数大跟堆比较
        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
        }
    }

    public static class DaddyComparator implements Comparator<Customer> { // 购买数小根堆比较
        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
        }
    }

    public static void main(String[] args) {
        // 手动自测
        int[] arr = {5, 3, 3, 1, 2, 2, 2, 5};
        boolean[] op = {false, true, true, true, true, true, true, false};
        System.out.println(showPrize(arr, op, 2));

        System.out.println(topK(arr, op, 2));

        // 使用对数器测试
        testMain();

    }

    /*
    暴力破解法：
     */
    public static List<List<Integer>> showPrize(int[] arr, boolean[] op, int k) {
        HashMap<Integer, Customer> map = new HashMap<Integer, Customer>();
        List<List<Integer>> ans = new ArrayList<>();
        List<Customer> candi = new ArrayList<>();
        List<Customer> daddy = new ArrayList<>();
        // 将所有的customer装入map中
        for (int i = 0; i < arr.length; i++) {
            Integer id = arr[i];
            boolean buyOrRefund = op[i];
            if (!buyOrRefund && !map.containsKey(id)) {
                ans.add(getCurDaddy(daddy));
                continue;// 用户bug为0，且退了一件货，下一个事件
            }

            // 1 map存储顾客行为，调教bug次数
            if (!map.containsKey(id)) {
                map.put(id, new Customer(id, 0, i)); // 第一次加入时，buy次数和time随后设置
            }
            Customer c = map.get(id);
            if (buyOrRefund) {
                c.buy++;
            } else {
                c.buy--;
            }
            if (c.buy == 0) {
                map.remove(id);
            }

            // 2 等候区和得奖区都不含c的意味着第一次进入，[(可选)调教进入两个区的time]，控制进入两个区
            if (!candi.contains(c) && !daddy.contains(c)) {
                if (daddy.size() < k) {
                    daddy.add(c);
                } else {
                    candi.add(c);
                }
            }

            // 3 清除两个区中buy=0的顾客，然后对比两个区buy的次数是否交换
            if (c.buy == 0) {
                candi.remove(c);
                daddy.remove(c);
            }
            candi.sort(new CandidateComparator());
            daddy.sort(new DaddyComparator());
            swap(candi, daddy, k, i);
            ans.add(getCurDaddy(daddy));
        }
        return ans;
    }

    /*
       候选区和得奖区判断是否进行交换，发生交换时要更改进入时间
    */
    private static void swap(List<Customer> candi, List<Customer> daddy, int k, int i) {
        if (candi.isEmpty()) return;

        if (daddy.size() < k) {
            Customer candiCustomer = candi.get(0);
            candiCustomer.enterTime = i;
            daddy.add(candiCustomer);
            candi.remove(candiCustomer);
        } else {
            if (candi.get(0).buy > daddy.get(0).buy) {
                Customer candiCustomer = candi.get(0);
                candiCustomer.enterTime = i;
                Customer daddyCustomer = daddy.get(0);
                daddyCustomer.enterTime = i;
                candi.set(0, daddyCustomer);
                daddy.set(0, candiCustomer);
            }
        }
    }

    /**
     * 获取当前获奖名单
     */
    private static List<Integer> getCurDaddy(List<Customer> daddy) {
        List<Integer> ans = new ArrayList<>();
        for (Customer c : daddy) {
            ans.add(c.id);
        }
        return ans;
    }

    /**
     * 此处使用加强堆对数据进行改写优化
     */
    public static class WhoIsDaddy {
        private HashMap<Integer, Customer> customerMap;
        private C12_HeapEnhance<Customer> candiHeap;
        private C12_HeapEnhance<Customer> daddyHeap;
        private final int daddyLimit;

        public WhoIsDaddy(int daddyLimit) {
            customerMap = new HashMap<>();
            candiHeap = new C12_HeapEnhance<>(new CandidateComparator());
            daddyHeap = new C12_HeapEnhance<>(new DaddyComparator());
            this.daddyLimit = daddyLimit;
        }

        public void operate(int enterTime, int id, boolean buyOrRefund) { // 对每次操作进行等候/得奖区域划分
            // 用户id购买次数为0且退货
            if (!customerMap.containsKey(id) && !buyOrRefund) return;

            // 第一次出现时，添加到map集合中
            if (!customerMap.containsKey(id)) {
                customerMap.put(id, new Customer(id, 0, enterTime));
            }

            // 处理用户的购买次数
            Customer c = customerMap.get(id);
            if (buyOrRefund) {
                c.buy++;
            } else {
                c.buy--;
            }
            if (c.buy == 0) {
                customerMap.remove(id);
            }

            // 处理两个区域内的用户操作数
            if (!candiHeap.contains(c) && !daddyHeap.contains(c)) {
                if (daddyHeap.size() < daddyLimit) {
                    daddyHeap.push(c); // 小根堆
                } else {
                    candiHeap.push(c); // 大跟堆
                }
            } else if (candiHeap.contains(c)) {
                if (c.buy == 0) {
                    candiHeap.remove(c);
                } else {
                    candiHeap.relocation(c);
                }
            } else if (daddyHeap.contains(c)) {
                if (c.buy == 0) {
                    daddyHeap.remove(c);
                } else {
                    daddyHeap.relocation(c);
                }
            }

            // 候选/得奖区域进行交换调整
            swapHeap(candiHeap, daddyHeap, daddyLimit, enterTime);
        }

        private void swapHeap(C12_HeapEnhance<Customer> candiHeap, C12_HeapEnhance<Customer> daddyHeap, int daddyLimit, int enterTime) {
            if (candiHeap.isEmpty()) return;

            if (daddyHeap.size() < daddyLimit) {
                Customer candiCustomer = candiHeap.pop();
                candiCustomer.enterTime = enterTime;
                daddyHeap.push(candiCustomer);
            } else {
                if (candiHeap.peek().buy > daddyHeap.peek().buy) {
                    Customer newCustomer = candiHeap.pop();
                    Customer oldCustomer = daddyHeap.pop();
                    newCustomer.enterTime = enterTime;
                    oldCustomer.enterTime = enterTime;
                    candiHeap.push(oldCustomer);
                    daddyHeap.push(newCustomer);
                }
            }
        }

        public List<Integer> getDaddy() {
            List<Integer> ans = new ArrayList<>();
            List<Customer> allElement = daddyHeap.getAllElement();
            for (Customer c : allElement) {
                ans.add(c.id);
            }
            return ans;
        }
    }

    public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        WhoIsDaddy whoIsDaddy = new WhoIsDaddy(k);
        for (int i = 0; i < arr.length; i++) {
            whoIsDaddy.operate(i, arr[i], op[i]);
            ans.add(whoIsDaddy.getDaddy());
        }
        return ans;
    }

    // 为了测试
    public static class Data {
        public int[] arr;
        public boolean[] op;

        public Data(int[] a, boolean[] o) {
            arr = a;
            op = o;
        }
    }

    // 为了测试
    public static Data randomData(int maxValue, int maxLen) {
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        boolean[] op = new boolean[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * maxValue);
            op[i] = Math.random() < 0.5 ? true : false;
        }
        return new Data(arr, op);
    }

    // 为了测试
    public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
        if (ans1.size() != ans2.size()) {
            return false;
        }
        for (int i = 0; i < ans1.size(); i++) {
            List<Integer> cur1 = ans1.get(i);
            List<Integer> cur2 = ans2.get(i);
            if (cur1.size() != cur2.size()) {
                return false;
            }
            cur1.sort((a, b) -> a - b);
            cur2.sort((a, b) -> a - b);
            for (int j = 0; j < cur1.size(); j++) {
                if (!cur1.get(j).equals(cur2.get(j))) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void testMain() {
        int maxValue = 10;
        int maxLen = 100;
        int maxK = 6;
        int testTimes = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            Data testData = randomData(maxValue, maxLen);
            int k = (int) (Math.random() * maxK) + 1;
            int[] arr = testData.arr;
            boolean[] op = testData.op;
            List<List<Integer>> ans1 = topK(arr, op, k);
            List<List<Integer>> ans2 = showPrize(arr, op, k);
            if (!sameAnswer(ans1, ans2)) {
                for (int j = 0; j < arr.length; j++) {
                    System.out.println(arr[j] + " , " + op[j]);
                }
                System.out.println(k);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("出错了！");
                break;
            }
        }
        System.out.println("测试结束");
    }

}



